

#include <iostream>
#include <vector>
#include <stack>
#include <unordered_set>
#include <algorithm>
using namespace std;

class Solution
{
public:
    int missingNumber1(vector<int>& nums)
    {
        int res = 0, n = nums.size();

        for (int i = 0; i <= n; ++i)
        {
            res ^= i;
        }
        for (const auto& e : nums)
        {
            res ^= e;
        }

        return res;
    }

    int missingNumber2(vector<int>& nums)
    {
        int res = 0;
        int n = nums.size();

        sort(nums.begin(), nums.end());
        for (int i = 0; i < n; ++i)
        {
            if (i != nums[i])
                return i;
        }

        return n;
    }

    int missingNumber3(vector<int>& nums)
    {
        int res = 0;
        unordered_set<int> hash;

        for (const auto& e : nums)
        {
            hash.insert(e);
        }

        for (int i = 0, n = nums.size(); i <= n; ++i)
        {
            if (!hash.count(i))
            {
                res = i;
                break;
            }
        }
        
        return res;
    }

    int missingNumber4(vector<int>& nums)
    {
        int n = nums.size();
        int allsum = n * (n + 1) / 2;

        for (const auto& e : nums)
        {
            allsum -= e;
        }

        return allsum;
    }

    int missingNumber5(vector<int>& nums)
    {
        int sum = 0, n = nums.size();

        for (const auto& e : nums)
        {
            sum += e;
        }

        return n * (n + 1) / 2 - sum;
    }

    int missingNumber6(vector<int>& nums)
    {
        int res = 0;

        for (int i = 0, n = nums.size(); i < n; ++i)
        {
            res ^= nums[i];
            res ^= i + 1;
        }

        return res;
    }
};

class MinStack
{
public:
    MinStack()
    {}

    void push(int val)
    {
        _st.push(val);
        if (_minst.empty() || val <= _minst.top())
            _minst.push(val);
    }

    void pop()
    {
        int top = _st.top();
        _st.pop();
        if (top == _minst.top())
            _minst.pop();
    }

    int top()
    {
        return _st.top();
    }

    int getMin()
    {
        return _minst.top();
    }
private:
    stack<int> _st;
    stack<int> _minst;
};

void Test1()
{
    vector<int> v = {3, 0, 1};
    Solution().missingNumber3(v);
}

int main()
{
	Test1();

	return 0;
}